package Algorithm.backTracking;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 51. N 皇后 https://leetcode.cn/problems/n-queens/
 * 题目简述：n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * 若两个皇后在同一直线或斜线上则能相互攻击。求对于整数n所有不同的 n 皇后问题 的解决方案。
 */
public class SolveNQueens {

    /**
     * 思路：每一行中必定都有一个棋子，否则若有一个空行则肯定有一行至少有两个棋子则不成立。因此可从上往下逐行遍历，在每一行中确定一个棋子的位置。
     * 回溯递归函数参数：（结果result，已选择路径，下一步路径选择列表第k行，已使用标记数组）
     * 回溯递归函数体：1.判断当前已选择路径是否已满足要求，若满足则返回
     *              2.遍历当前选择列表第k行[0, n-1]位置。可行性剪枝：若[k][i]正上方或者左/右斜上方已有棋子，则此位置不能用，略过。
     *                  否则将选择加入路径，递归下一步的选择列表，完毕后回溯撤销上一步路径选择，继续遍历同层中的其它路径
     */
    int n;
    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        List<List<String>> result = new ArrayList<>();
        Deque<String> path = new ArrayDeque<>();
        boolean[][] used = new boolean[n][n];
        backTracing(result, path, 0, used);
        return result;
    }

    public void backTracing(List<List<String>> result, Deque<String> path, int k, boolean[][] used) {
        if(path.size() == n) { //若路径长度已达到要求则添加结果然后return
            result.add(new ArrayList<>(path));
            return;
        }
        //路径选择列表：当前行中[0, n-1]的位置
        for(int i = 0;i < n;i++) {
            //可行性剪枝：若[k][i]正上方或者左/右斜上方已有棋子，则此位置不能用，略过
            boolean flag = true;
            for(int j = k-1;flag && j >= 0;j--) { //检查正上方
                if(used[j][i]) flag = false;
            }
            for(int j = Math.min(k, i);flag && j > 0;j--) { //检查左斜上方
                if(used[k-j][i-j]) flag = false;
            }
            for(int j = 1;flag && k-j >= 0 && i+j < n;j++) { //检查右斜上方
                if(used[k-j][i+j]) flag = false;
            }
            if(!flag) continue;
            //若此位置可以使用，则添加路径，并将对应位置标记为已使用
            path.add(buildColumn(i));
            used[k][i] = true;
            //递归下一步路径选择列表
            backTracing(result, path, k+1, used);
            //回溯：撤销上一步选择和使用标记，继续遍历同层其他路径
            path.removeLast();
            used[k][i] = false;
        }
    }

    public String buildColumn(int i) {
        StringBuilder builder = new StringBuilder();
        for (int j = 0;j < n;j++) {
            if (j == i) builder.append('Q');
            else builder.append('.');
        }
        return builder.toString();
    }
}
